Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Algoritmos meta-heurísticos para a solução do problema do caixeiro viajante com múltiplas caronas

The Traveling Salesman with Multiple Ridesharing (TSP-MR) is a type of the Capacitated Traveling Salesman, which presents the possibility of sharing seats with passengers taking advantage of the paths the salesman travels through his cycle. The salesman shares the cost of a path with the boarded passengers. This model can portray a real situation in which, for example, drivers are willing to share parts of a trip with tourists that wish to move between two locations visited by the driver’s route, accepting to share the vehicle with other individuals visiting other locations within the cycle. This work proposes a mathematical formulation for the problem, and an exact and metaheuristics algorithms for its solution, comparing them.

Feiras livres : cidades de um só dia, aprendizados para a vida inteira

La tesis problematiza constelaciones creativas de saberes marcados por múltiples subjetividades en un espacio singular de las ciudades: la feria libre. Lugar de cambios financieros, pero también afectivos, simbólicos y míticos, ese espacio se mantiene al lado de los lugares comerciales asépticos y climatizados como son los supermercados e hipermercados de los espacios urbanos y de las metrópolis. Las ferias, por su carácter itinerante y sus personajes nómades modernos, son capaces de suscitar múltiples observaciones, divagaciones, afecciones y construcción de conocimientos. En la feria libre del barrio de Alecrim en la ciudad de Natal-RN/Brasil, principal contexto de referencia de esta investigación, en medio de tantos estímulos movilizadores de los órganos de los sentidos, salta a los ojos el elevado contingente de niños y adolescentes ejerciendo las múltiples actividades laborales. En Brasil el trabajo infantil es encajado en prohibiciones prescritas por leyes que recubren singularidades. Sin la pretensión de negar la importancia de tales convenciones y reglas, las reflexiones aquí puestas ultrapasan las amarras homogeneizantes del discurso oficial instituido de prohibición, problematizando a partir de la feria la idea de una caótica y pulsante aula al aire libre en la cual se construyen saberes más próximos de una lógica del sensible (Claude Lévi-Strauss). La feria es un laboratorio de construcción de conocimientos pertinentes (Edgar Morin), aquellos que religan fenómeno y contexto sin oponer manipulación y tiempo real de aplicabilidad de los saberes construidos. En esa escuela sin paredes, puertas, ventanas, cuadros negros o programas, los saberes de la tradición (Conceição Almeida) son probados y compartidos por niños y adolescentes que viven constantemente con un tipo de cambio de bienes y palabras en permanente construcción. En los puestos de la feria y para más allá de ellos encontramos sujetos híbridos (Bruno Latour) que se estructuran por medio de mecanismos creativos capaces de hacerlos navegar en las incertidumbres caóticas de sus vidas. Los aprendizajes de la feria fueron o son la pulsión de reinvención de esos sujetos aparentemente encarcelados en el conformismo como fatalidad última, portadores de historias embarazadas de simbologías tristes y felices que exponen la cara de un humano en permanente combustión, construcción e incertidumbre

Metodologia para modelagem, validação e programação de controladores lógicos industriais usando statecharts básicos

Due of industrial informatics several attempts have been done to develop notations and semantics, which are used for classifying and describing different kind of system behavior, particularly in the modeling phase. Such attempts provide the infrastructure to resolve some real problems of engineering and construct practical systems that aim at, mainly, to increase the productivity, quality, and security of the process. Despite the many studies that have attempted to develop friendly methods for industrial controller programming, they are still programmed by conventional trial-and-error methods and, in practice, there is little written documentation on these systems. The ideal solution would be to use a computational environment that allows industrial engineers to implement the system using high-level language and that follows international standards. Accordingly, this work proposes a methodology for plant and control modelling of the discrete event systems that include sequential, parallel and timed operations, using a formalism based on Statecharts, denominated Basic Statechart (BSC). The methodology also permits automatic procedures to validate and implement these systems. To validate our methodology, we presented two case studies with typical examples of the manufacturing sector. The first example shows a sequential control for a tagged machine, which is used to illustrated dependences between the devices of the plant. In the second example, we discuss more than one strategy for controlling a manufacturing cell. The model with no control has 72 states (distinct configurations) and, the model with sequential control generated 20 different states, but they only act in 8 distinct configurations. The model with parallel control generated 210 different states, but these 210 configurations act only in 26 distinct configurations, therefore, one strategy control less restrictive than previous. Lastly, we presented one example for highlight the modular characteristic of our methodology, which it is very important to maintenance of applications. In this example, the sensors for identifying pieces in the plant were removed. So, changes in the control model are needed to transmit the information of the input buffer sensor to the others positions of the cell

Um estudo algorítmico da programação da intervenção de sondas de produção

This work approaches the Scheduling Workover Rigs Problem (SWRP) to maintain the wells of an oil field, although difficult to resolve, is extremely important economical, technical and environmental. A mathematical formulation of this problem is presented, where an algorithmic approach was developed. The problem can be considered to find the best scheduling service to the wells by the workover rigs, taking into account the minimization of the composition related to the costs of the workover rigs and the total loss of oil suffered by the wells. This problem is similar to the Vehicle Routing Problem (VRP), which is classified as belonging to the NP-hard class. The goal of this research is to develop an algorithmic approach to solve the SWRP, using the fundamentals of metaheuristics like Memetic Algorithm and GRASP. Instances are generated for the tests to analyze the computational performance of the approaches mentioned above, using data that are close to reality. Thereafter, is performed a comparison of performance and quality of the results obtained by each one of techniques used

EUPAT for WoW: Uma ferramenta de assistência à programação por usuário final

Neste trabalho, apresentamos uma ferramenta cujo intuito é auxiliar não-programadores, jogadores de videogame, na criação de extensões na forma de Add-ons para World of Warcraft, o jogo online. Nele, o usuário pode criar extensões customizando completamente sua interface, de forma a reinventar a sua experiência de jogo e melhorar sua jogabilidade. A criação de extensões para aplicativos e jogos surgiu da crescente necessidade de fornecer aos usuários mecanismos eficientes de Programação por Usuário Final, permitindo que os mesmos preenchessem suas necessidades singulares através da criação, customização e especificação de extensões em software. Em World of Warcraft mais especificamente, os Add-ons exploram um tipo de extensão na qual os jogadores passam a programar sua própria interface de usuário ou a fazer uso de interfaces criadas por outros usuários. No entanto, realizar a programação dessas extensões - os Add-ons - não é uma tarefa fácil. Dentro deste contexto, desenvolvemos a ferramenta EUPAT for WoW (do inglês, End-User Programming Assistance Tool for World of Warcraft) que oferece assistência à criação de Add-ons. Além disso, investigamos como usuários jogadores com e sem conhecimento de programação são beneficiados. Os resultados desta pesquisa permitiram refletir sobre as estratégias de assistência de programação por usuário final no contexto de jogos

Utilizando programação orientada a aspectos no projeto de sistemas hardware desenvolvidos com SystemC

New programming language paradigms have commonly been tested and eventually incorporated into hardware description languages. Recently, aspect-oriented programming (AOP) has shown successful in improving the modularity of object-oriented and structured languages such Java, C++ and C. Thus, one can expect that, using AOP, one can improve the understanding of the hardware systems under design, as well as make its components more reusable and easier to maintain. We apply AOP in applications developed using the SystemC library. Several examples will be presented illustrating how to combine AOP and SystemC. During the presentation of these examples, the benefits of this new approach will also be discussed

POPT: uma abordagem de ensino de programação orientada a problema e testes

There is a growing interest of the Computer Science education community for including testing concepts on introductory programming courses. Aiming at contributing to this issue, we introduce POPT, a Problem-Oriented Programming and Testing approach for Introductory Programming Courses. POPT main goal is to improve the traditional method of teaching introductory programming that concentrates mainly on implementation and neglects testing. POPT extends POP (Problem Oriented Programing) methodology proposed on the PhD Thesis of Andrea Mendonça (UFCG). In both methodologies POPT and POP, students skills in dealing with ill-defined problems must be developed since the first programming courses. In POPT however, students are stimulated to clarify ill-defined problem specifications, guided by de definition of test cases (in a table-like manner). This paper presents POPT, and TestBoot a tool developed to support the methodology. In order to evaluate the approach a case study and a controlled experiment (which adopted the Latin Square design) were performed. In an Introductory Programming course of Computer Science and Software Engineering Graduation Programs at the Federal University of Rio Grande do Norte, Brazil. The study results have shown that, when compared to a Blind Testing approach, POPT stimulates the implementation of programs of better external quality the first program version submitted by POPT students passed in twice the number of test cases (professor-defined ones) when compared to non-POPT students. Moreover, POPT students submitted fewer program versions and spent more time to submit the first version to the automatic evaluation system, which lead us to think that POPT students are stimulated to think better about the solution they are implementing. The controlled experiment confirmed the influence of the proposed methodology on the quality of the code developed by POPT students

Formulações e algoritmos para o problema das p-medianas heterogêneo livre de penalidade

This work presents a new model for the Heterogeneous p-median Problem (HPM), proposed to recover the hidden category structures present in the data provided by a sorting task procedure, a popular approach to understand heterogeneous individual’s perception of products and brands. This new model is named as the Penalty-free Heterogeneous p-median Problem (PFHPM), a single-objective version of the original problem, the HPM. The main parameter in the HPM is also eliminated, the penalty factor. It is responsible for the weighting of the objective function terms. The adjusting of this parameter controls the way that the model recovers the hidden category structures present in data, and depends on a broad knowledge of the problem. Additionally, two complementary formulations for the PFHPM are shown, both mixed integer linear programming problems. From these additional formulations lower-bounds were obtained for the PFHPM. These values were used to validate a specialized Variable Neighborhood Search (VNS) algorithm, proposed to solve the PFHPM. This algorithm provided good quality solutions for the PFHPM, solving artificial generated instances from a Monte Carlo Simulation and real data instances, even with limited computational resources. Statistical analyses presented in this work suggest that the new algorithm and model, the PFHPM, can recover more accurately the original category structures related to heterogeneous individual’s perceptions than the original model and algorithm, the HPM. Finally, an illustrative application of the PFHPM is presented, as well as some insights about some new possibilities for it, extending the new model to fuzzy environments

Um Framework para criação de jogos voltados para o ensino de lógica de programação

Digital games have been used as aiding tool for transmission of knowledge, allowing faster dissemination of content. Using this strategy of disseminating logical reasoning development for basic school children can be the motivating gear that helps in the learning process for any area. In this context, many games can be created and provided for the use of teacher and student. However, the complexity of construction of these games becomes a obstacle which can, often, prevent their construction. Thus, this paper presents a framework for creating games, which teach programming logic, presenting from their conception to their integration with the visual programming environment (Blockly) and scenarios created in HTML5.

Estudo e desenvolvimento de algoritmos criptográficos para redes de sensores sem fio, utilizando técnicas de programação genética

Cryptography is the main form to obtain security in any network. Even in networks with great energy consumption restrictions, processing and memory limitations, as the Wireless Sensors Networks (WSN), this is no different. Aiming to improve the cryptography performance, security and the lifetime of these networks, we propose a new cryptographic algorithm developed through the Genetic Programming (GP) techniques. For the development of the cryptographic algorithm’s fitness criteria, established by the genetic GP, nine new cryptographic algorithms were tested: AES, Blowfish, DES, RC6, Skipjack, Twofish, T-DES, XTEA and XXTEA. Starting from these tests, fitness functions was build taking into account the execution time, occupied memory space, maximum deviation, irregular deviation and correlation coefficient. After obtaining the genetic GP, the CRYSEED and CRYSEED2 was created, algorithms for the 8-bits devices, optimized for WSNs, i.e., with low complexity, few memory consumption and good security for sensing and instrumentation applications.

Estudo e desenvolvimento de algoritmos criptográficos para redes de sensores sem fio, utilizando técnicas de programação genética

Cryptography is the main form to obtain security in any network. Even in networks with great energy consumption restrictions, processing and memory limitations, as the Wireless Sensors Networks (WSN), this is no different. Aiming to improve the cryptography performance, security and the lifetime of these networks, we propose a new cryptographic algorithm developed through the Genetic Programming (GP) techniques. For the development of the cryptographic algorithm’s fitness criteria, established by the genetic GP, nine new cryptographic algorithms were tested: AES, Blowfish, DES, RC6, Skipjack, Twofish, T-DES, XTEA and XXTEA. Starting from these tests, fitness functions was build taking into account the execution time, occupied memory space, maximum deviation, irregular deviation and correlation coefficient. After obtaining the genetic GP, the CRYSEED and CRYSEED2 was created, algorithms for the 8-bits devices, optimized for WSNs, i.e., with low complexity, few memory consumption and good security for sensing and instrumentation applications.

JCML: A specification language for the runtime verification of Java Card programs

COSTA, Umberto Souza; MOREIRA, Anamaria Martins; MUSICANTE, Matin A.; SOUZA NETO, Plácido A. JCML: A specification language for the runtime verification of Java Card programs. Science of Computer Programming. [S.l]: [s.n], 2010.

Natureza morta...edifício com vida: uma arquitetura sustentável para o Serviço de Verificação de Óbitos

Sustainability in buildings, while reducing the impact on the environment, contributes to the promotion of social welfare, to increase the health and productivity of occupants. The search for a way of build that meets the aspirations and development of humanity without, however, represent degradation of the environment, has become the great challenge of contemporary architecture. It is considered that the incorporation of principles that provide a sustainable building with careful choices of design solutions contribute to a better economic and thermal performance of the building, as well as functional and psychological comfort to its users. Based on this general understanding, this paper presents an architecture project aimed to health care whose the solutions adopted follow carefully the relevant legislation and sets his sights on the theme of sustainability. The methodology began with studies on the themes of verification service of deaths, sustainability and those application in construction developed through research in academic studies and analysis of architectural projects, using them like reference for the solutions adopted. Within the project analysis was performed a visit to the verification service of deaths in the city of Palmas in Tocantins, subsidizing information that, plus the relevant legislation, led to functional programming and pre-dimensional of the building to be designed. The result of this programming environments were individual records with information from environmental restrictions, space required for the development of activities, desirable flow and sustainability strategies, that can be considered as the first product of relevance of the professional master's degree. Finally we have outlined the basic design architecture of a Verification Service of Death SVO/RN (in portuguese), whose process of projecting defined as a guiding line of work four points: the use of bioclimatic architecture as the main feature projectual, the use of resources would provide minimal harm to the environment, the use of modulation and structure to the building as a form of rationalization and finally the search for solutions that ensure environmental and psychological comfort to users. Importantly to highlight that, besides owning a rare theme in literature that refers to architectural projects, the whole project was drawn up with foundations in projective criteria that contribute to environmental sustainability, with emphasis on thermal performance, energy efficiency and reuse of rainwater

Todo Brasileiro merece nível A : habitação multifamiliar para o programa minha casa minha vida energeticamente eficiente

This thesis describes the theoretical, methodological and programmatic proposal for a multifamily residential building located in the urban expansion area of Parnamirim/RN, inserted in the program Minha Casa Minha Vida and level of energy efficiency "A", as the RegulamentoTécnico de Qualidade (RTQ-R/INMETRO) for residential buildings. The development project initially consists of procedures as the study of theoretical, architectural programming and cases studies. With the delimitation of a field solution, situated between the reference and the context, proposals are studied to determine the solution and architectural detailing of the proposal. The architectural program was built based on the method of Problem Seeking (Peña and Parshall, 2001) and research has highlighted aspects of reducing the environmental impact and of the program Minha Casa Minha Vida , among others. The design process was characterized by the incorporation of aspects reviewed and programmed, seeking them compatible and have an economically viable building, socio-spatial quality and energy efficient. The results show that it is possible to obtain a building that meets the constraints of the program that provides housing and energy efficiency level A - and many other environmental qualities and constructive, particularly through architectural design